package experiment2;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
	    int[] arr = { 40, 37, 65, 97, 76, 15, 27, 13, 11, 9 };
	    quickSort(arr, 0, arr.length - 1);
	    System.out.println(Arrays.toString(arr));
	}

	private static void quickSort(int[] arr, int low, int hight) {
	    int i = low;
	    int j = hight;

	    if (i > j) {
	        return;
	    }

	    int key = arr[low];

	    while (true) {

	        while (j > i) {
	            if (arr[j] < key) {
	                swap(arr, i, j);
	                break;
	            } else {
	                j--;
	            }
	        }


	        while (i < j) {
	            if (arr[i] > key) {
	                swap(arr, i, j);
	                break;
	            } else {
	                i++;
	            }
	        }
	        if (i == j) {
	            break;
	        }

	    }
	    quickSort(arr, low, i - 1);
	    quickSort(arr, i + 1, hight);

	}

	private static void swap(int[] arr, int i, int j) {
	    int temp = arr[i];
	    arr[i] = arr[j];
	    arr[j] = temp;
	}
}
